package org.lql.algo.codecrush.hot100.dynamicProgramming;

/**
 * @author: liangqinglong
 * @date: 2025-09-14 11:12
 * @description: 279. 完全平方数 <a href="https://leetcode.cn/problems/perfect-squares/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class NumSquares {

	public int numSquares(int n) {
		int[] dp = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			dp[i] = i;
			for (int j = 1; j * j <= i; j++) {
				dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
			}
		}
		return dp[n];
	}

	public static void main(String[] args) {
		NumSquares numSquares = new NumSquares();
		System.out.println(numSquares.numSquares(12));
		System.out.println(numSquares.numSquares(13));
	}
}
